import java.util.LinkedList;
import java.util.Queue;

class Solution1926 {
   int [] dx = {0,0,1,-1} ; 
   int[] dy = {1,-1,0,0} ; 

    public int nearestExit(char[][] maze, int[] entrance) {
      return bfs(maze , entrance);
    }
    private int bfs (char[][]maze , int[] entrance){
       Queue<int[]> queue = new LinkedList<>() ;
       int m = maze.length , n = maze[0].length ;
       queue.add(entrance) ;
       boolean[][] hash = new boolean[m][n];
       int len = 0 ; 
       hash[entrance[0]][entrance[1]] = true ;
       while(!queue.isEmpty()){
         int size = queue.size() ;
         len ++ ; 
         for(int i=0;i < size ; i ++){
           int[] arr = queue.poll() ;
           int a = arr[0] , b = arr[1] ; 
           for(int j=0;  j < 4 ; j ++){
            int x = a+dx[j] , y = b+dy[j] ; 
            if(x>=0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !hash[x][y]){
                // 判断是否已经到出口了
               if(x == 0 || x == m-1 || y == 0 || y == n-1){
                return len ; 
               }
                queue.add(new int[]{x , y}) ; 
                hash[x][y] = true ;
            }
           }

         }
         
       }
      
      return -1 ;
    }
}